COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\section{General tree recursion.}
C00012 00003	\section{Non-structural recursions.}
C00017 00004	\section{Solving a LISP programming problem.}
C00036 00005	\section{Lots of LISP functions to program.}
C00064 ENDMK
C⊗;
\section{General tree recursion.}
\label{treerec}

	A tree structure is either a leaf or a node together with
a collection of immediate successors which are also trees.  Many data structures
can be viewed as trees.  For example, S-expressions are trees with leaves as atoms,
and each non-leaf tree has two successors given by the /car\// and the /cdr/.  
More generally, the structures described in section (qsect{subsection strucrec})
can be thought of as tree-like structures with the basic elements as leaves,
and each non-leaf tree having immediate successors given by the selector
functions for the particular type of node.  These structures all have two things
in common.  Namely, (i) each kind of node has a fixed number of successors and
(ii) these successors are already present as parts of the original tree.

	Another kind of tree is given by an initial position
together with a /successors\// function from which we may obtain the immediate
successors of any position (of relevance).  A node may have any
number of successors, and parts of the trees are built as needed.
Functions on such trees typically involve two processes, one for recognizing
and dealing with leaves and one for processing a collection of succesors.
(Of course the two processes interact recursively.)  

	Consider the problem for searching a tree for a position having some
particular property.   We can write a program that describes a depth
first  search independent of the property or kind of tree.
It can be used to search specific trees  by defining the
three auxiliary functions /successors/, /ter/, and /lose\// for the particular
problem.  We have
%(bb tex '(search))
$$\label{fcnsearch}
\vbox{
\hbox{\hskip0\unit $/search\// /p\// ← $}
\hbox{\hskip4\unit $    \qif  /lose\// /p\// \qthen  |LOSE| \qelsif  /ter\// 
/p\// \qthen  /p\// \qelse  /searchlis\// /successors\// /p\//$}
}
$$
where
%(bb tex '(searchlis))
$$\label{fcnsearchlis}
\vbox{
\hbox{\hskip0\unit $/searchlis\// /u\// ← $}
\hbox{\hskip4\unit $    \qif  \qn /u\// \qthen  |LOSE|$}
\hbox{\hskip4\unit $    \qelse  {/search\// \qa /u\//}[λ/x\//: \qif  /x\// 
\qeq |LOSE| \qthen  /searchlis\// \qd /u\// \qelse  /x\//]$}
}
$$

In the applications, we start with a position /p0/, and we
are looking for a win in the successor tree of /p0/.  Certain
positions lose and there is no point looking at their successors.
This is decided by the predicate /lose/.  A position is a win if
it doesn't lose and it satisfies the predicate /ter/.  The
successors of a position are given by the function /successors/,
and the value of /search\ p/ is the winning position.  No
non-losing position should have the name |LOSE| or the function won't
work properly.

	One application is finding a path from an initial node to
a final node in a graph represented by a list structure as described
in chapter I{}.  A position is a path starting from the initial node
and continuing to some intermediate node and is represented by a
list of its nodes in reverse order.  The three functions for this
application are
%(putprop 'successors (get 'successors 's1) 'expr)
%(bb tex '(lose ter successors))
$$\label{fcnlose}\label{fcnter}\label{fcnsuccessors}
\vbox{
\hbox{\hskip0\unit $/lose\// /p\// ← \qa /p\// ε \qd /p\//$}
\medskip

\hbox{\hskip0\unit $/ter\// /p\// ← \qa /p\// \qeq /final\//$}
\medskip

\hbox{\hskip0\unit $/successors\// /p\// ← /mapcar\//[[λ/x\//: /x\// \qcons 
 /p\//], \qd /assoc\//[\qa /p\//, /graph\//]]$}
}
$$

The node we are proposing to visit next loses if it is already in
the path, as that means we have been here before.  The successors to a position
are all of those positions immediately reachable from the current node.
In our list notation for a graph the immediately reachable nodes are those
on the list associated with the current node in /graph/.  A position is
terminal if the current node is the desired goal /final/.  

	/search\// is used when we want to search a tree of possibilities
for a solution to a problem.
Naturally we can do other things with tree search recursion than just
search.  For example we may want to find all solutions
to a problem.  This can be done with a function /allsol\// that uses
the same /lose/, /ter/, and /successors\// functions as does /search/. 
The simplest way to write /allsol\// is
%(bb tex '(allsol1))
$$\label{fcnallsol}
\vbox{
\hbox{\hskip0\unit $/allsol1\// /p\// ← $}
\hbox{\hskip4\unit $    \qif  /lose\// /p\// \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /ter\// /p\// \qthen  </p\//>$}
\hbox{\hskip4\unit $    \qelse  /mapapp\//[/allsol1\//, /successors\// 
/p\//]$}
}
$$
where
$$\label{fcnmapapp}
%(bb tex '(mapapp))
\vbox{
\hbox{\hskip0\unit $/mapapp\//[/fn\//, /u\//] ← \qif  \qn /u\// \qthen 
 \qNIL  \qelse  /fn\// \qa /u\// * /mapapp\//[/fn\//, \qd /u\//]$}
}
$$

This form of the function is somewhat inefficient because of all the
/append\//ing.  A more efficient form uses an auxiliary function as follows: 
$$\label{fcnallsola}
%(bb tex '(allsol allsola allsolb))
\vbox{
\hbox{\hskip0\unit $/allsol\// /p\// ← /allsola\//[/p\//, \qNIL ]$}
\medskip

\hbox{\hskip0\unit $/allsola\//[/p\//, /found\//] ← $}
\hbox{\hskip4\unit $    \qif  /lose\// /p\// \qthen  /found\//$}
\hbox{\hskip4\unit $    \qelsif  /ter\// /p\// \qthen  /p\// \qcons  /found\//$}
\hbox{\hskip4\unit $    \qelse  /allsolb\//[/successors\// /p\//, /found\//]$}
\medskip

\hbox{\hskip0\unit $/allsolb\//[/u\//, /found\//] ← \qif  \qn /u\// \qthen 
 /found\// \qelse  /allsolb\//[\qd /u\//, /allsola\//[\qa /u\//, /found\//]]$}
}
$$

The recursive program structure that arises here is common when a list
is to be formed by recurring through a list structure.

	We will give further applications of and variations on this form
of tree search recursion in Chapter (SECTION SEARCH).
\section{Non-structural recursions.}
\label{nonstruc}
	Not all recursions are structural.  Any recursion may be
put in the general form
$$
%(bb tex '(f7))
\vbox{
\hbox{\hskip0\unit $/f/ /x/ ← \qif  /p/ /x/ \qthen  /g/ /x/ \qelse  /f/ 
/h/ /x/$}
}
$$
where several variables may have to be /cons\//ed together to make the one
variable /x/, 
but unless the functions /g/ and /h/ have some special relation,
there is no reason to suppose that the computation will terminate.

	For example,
$$
%(bb tex '(f8))
% Definition changed to give n/2 and 3n+1 in nicer notation
\vbox{
\hbox{\hskip0\unit $/f/ /n/ ← $}
\hbox{\hskip4\unit $    \qif  /n/ \qequal 1 \qthen  1$}
\hbox{\hskip4\unit $    \qelsif  /even/ /n/ \qthen  /f/ [/n/\div 2]$}
\hbox{\hskip4\unit $    \qelse  /f/ [3/n/ + 1]$}
}
$$
terminates for all positive integer values of /n/ that have been tested,
but no-one has been able to determine whether it always terminates.  If
you want to experiment, try small values of /n/ get an idea of how the
function seems to behave, and then try $/n/=27$.

	The function
$$
%(bb tex '(sack))
\vbox{
\hbox{\hskip0\unit $/sack/[/x/, /y\//] ← $}
\hbox{\hskip4\unit $    \qif  \qat /x/ \qthen  /x/ \qcons  /y/$}
\hbox{\hskip4\unit $    \qelsif  \qat /y/ \qthen  /sack/[\qa /x/, \qd /x\//]$}
\hbox{\hskip4\unit $    \qelse  /sack/[\qd /x/, /sack/[/x/, \qd /y\//]]$}
}
$$
is an S-expression analog of the function /ack/ defined in 
section (qsect{subsection numrec})
on numerical recursion.  Unlike /flat/ the occurrence of double recursion
$(/sack/[\ldots,/sack/[\ldots]])$ is crucial.  Like /ack/ this function cannot
be defined by any collection of simple recursive schemata.
It is a kind of structural recursion.

	Takeuchi defined the function
$$
%(bb tex '(tak))
\vbox{
\hbox{\hskip0\unit $/tak/[/x/, /y/, /z\//] ← $}
\hbox{\hskip4\unit $    \qif  /x/ \qgt  /y/ \qthen  $}
\hbox{\hskip8\unit $        /tak/[/tak/[/x/ - 1, /y/, /z\//], $}
\hbox{\hskip14\unit $              /tak/[/y/ - 1, /z/, /x\//], $}
\hbox{\hskip14\unit $              /tak/[/z/ - 1, /x/, /y\//]]$}
\hbox{\hskip4\unit $    \qelse  /z/$}
}
$$
to test LISP systems on a program that would run a long time but not
use much storage or stack.  It has been shown to always terminate for
integer arguments.  Most likely it also always terminates for real
arguments, but this seems harder to show.

	The interpreter /eval/ is itself a non-structural recursion,
and whether it terminates depends on the expressions it is given
to evaluate.
\section{Solving a LISP programming problem.}
\label{soln}

	In this section we present a programming problem
that is somewhat more complex than the examples of earlier sections
and work out the solution in detail, the purpose being to help you
get started thinking recursively and to show how a typical problem
might be approached.   After describing the function we wish to compute,
we will write programs for two simpler but related functions in order to better
understand various aspects of the control structure and information
flow needed in the main computation.  This is a useful technique in
problem solving in general, the trick of course is to find a simplification
which produces a problem that you can solve and whose solution is
useful in solving the original problem.   Having written programs for 
these simpler functions, we then use the insight gained to 
to solve the main problem.

	The problem has to do with ``lists of lists'' or L-lists.  An L-list
is either the empty list, \qNIL, or an atom /cons\//ed onto the front of
an L-list, or an L-list /cons\//ed onto the front of an L-list.   Thus
|(A (A B) C)| is an L-list, but |(A (B . C) D)| is not.   Although
this class of S-expressions is less general than the usual LISP notion
of list, it is more uniform.  The
computation of a function on L-lists may use the value of the function
on the /car/ of the L-list (when it is non-atomic) as well as on the 
/cdr/ as both are again L-lists.

	The function /allsubsub/ returns a list of all occurrences of an 
L-list /u/ as a sublist or as a sublist of a sublist of an L-list /v/.  
For example |(A A)| occurs three times as a subsublist of |(A A A B A A)|
and |(A)| occurs 4 times in |(A (B (A A)) (C (((A)))))|.

	We begin with a simpler function restricted to lists of atoms.
Thus we wish to compute the function /allsub/ that returns a list of all 
occurrences of a list of atoms /u/ as a sublist of another list of atoms /v/.  
The first thing to do is decide on the representation of an
occurrence of one list as a sublist of another list.  In the case of 
lists of atoms, a fairly natural solution is to represent an occurrence of a
particular sublist as the number /n/ corresponding to position in the list 
of the beginning of that occurrence.  Thus  
$$
/allsub\//[|(A A),(A A A B A A)|] = |(1 2 5)|.
$$

	To compute $/allsub\//[/u/,/v\//]$, if /v/ is \qNIL\ then the answer is \qNIL.
Otherwise, imagine that we know the answer for \qd /v/.
Then there are two possiblities.
Either /u/ ``agrees with'' /v/ (/v/ may be longer than /u/, but up to the end of /u/ 
the elements of /v/ and /u/ are the same), or not.  If not, the answer is
just the result for \qd /v/, otherwise we add the current
position to the result for \qd /v/.  This analysis
suggests that we will need an additional argument to keep track of
the current position.  Thus we define a function $/allsub1/[/u/,/v/,/p\//] $
where the argument /p/ is intended to correspond to the position of
the argument /v/ in the initial list.  If /v/ is \qNIL\ then the
result is \qNIL.  Otherwise suppose we know the value of 
$/allsub1/[/u/,\qd /v/,/p/+1]$
then we either add /p/ onto that value or return it unchanged according to
whether or not /u/ agrees with /v/.  Assuming we have a suitable definition of 
/agrees/, the above analysis leads to the following definitions:
$$
\label{fcnallsub}
%(bb tex '(allsub allsub1))
\vbox{
\hbox{\hskip0\unit $/allsub/[/u/, /v\//] ← /allsub1/[/u/, /v/, 1]$}
\medskip
\hbox{\hskip0\unit $/allsub1/[/u/, /v/, /p\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /agrees/[/u/, /v\//] \qthen  $}
\hbox{\hskip8\unit $        /p/ \qcons  /allsub1/[/u/, \qd /v/, /add1/ 
/p\//]$}
\hbox{\hskip4\unit $    \qelse  /allsub1/[/u/, \qd /v/, /add1/ /p\//]$}
}
$$

	It remains for us to write the definition of
$/agrees/[/u/,/v\//]$ 
which determines whether or not /u/ matches the beginning of /v/.  
This is easy.  If /u/ is \qNIL\ then we have gotten to the end of /u/ 
with out finding a disagreement and we return \qT.   If /v/ is \qNIL\ (and /u/ is not)
then we return \qNIL\ and /u/ does not agree with the beginning of /v/.  
Otherwise the result is \qT\ only if $\qa/u/=\qa/v/$ 
and the /cdr\//s of /u/ and /v/ 
agree.  Thus
$$
\label{fcnagrees}
%(bb tex '(agrees))
\vbox{
\hbox{\hskip0\unit $/agrees/[/u/, /v\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /u/ \qthen  \qT $}
\hbox{\hskip4\unit $    \qelsif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelse  \qa /u/ \qequal \qa /v/ \qand /agrees/[\qd 
/u/, \qd /v\//]$}
}
$$
The internal forms of the above definitions are
{\tt\obeyspaces\obeylines
    (DEFUN ALLSUB (U V) (ALLSUB1 U V 1)) 

    (DEFUN ALLSUB1 (U V P) 
           (COND ((NULL V) NIL)
                 ((AGREES U V) (CONS P (ALLSUB1 U (CDR V) (ADD1 P))))
                 (T (ALLSUB1 U (CDR V) (ADD1 P))))) 

    (DEFUN AGREES (U V) 
           (COND ((NULL U) T)
                 ((NULL V) NIL)
                 (T (AND (EQUAL (CAR U) (CAR V))
                         (AGREES (CDR U) (CDR V)))))) 
}

	Now we return to the /allsubsub\// problem. 
As with the simpler case, we must first decide how to represent an occurrence 
of an L-list as a subsublist of an L-list.  Again we need only represent the
position where the list comparison begins.  Consider an arbitrary point, /p/,  in an
L-list.  Either it is an element of the list, or is contained in one of the
elements of the list.  In the first case the position /n/ of the element is
sufficient, in the second case we need the position /n/ of the element together
with the position of the point /p/ relative to that element.
Thus in the first case we take the list containing only the number /n/ and
in the second case we add /n/ onto the list representing the position of /p/ 
in the /n\//th element of the list.  Using this representation we have
$$
/allsubsub/[|(A),(A (B (A A)) (C (((A)))))|] = |((1) (2 2 1) (2 2 2) (3 2 1 1 1))|.
$$

	To construct the desired list of positions we check for a agreement of /u/ 
at each position and add matching positions to the result.   (Actually 
we will see that some positions can be ruled out with out explicitly checking 
for agreement.)  In particular, we will need to pass around sufficient information
to be able to construct a representation of the current position whenever an
agreement
is found.  Let us consider the simpler problem of computing $/allpos/[/v\//]$, a list
of all the positions in /v/.  A program for this  can easily be modified 
to list only those positions satisfying the ``agrees'' condition.
A definition of /allpos/ can be obtained by recalling the discussion about of how
a position is to be represented.  Namely if /n/ is the position of /v/ 
in the list of which /v/ is a tail then
(i) if /v/ is \qNIL\ then there are no positions and the answer is \qNIL,
(ii) \qa/v/ is an atom then add $<n>$ to the list of positions in \qd /v/
passing $/n/+1$ as the current position number
(iii) otherwise compute the list of positions in \qa/v/ (relative to \qa/v/),
tack /n/ onto the front of each position, append this onto the list of
positions in \qd /v/ (again passing $/n/+1$) and finally add the current
position, $<n>$, to the result.   Thus we have
$$
\label{fcnallpos}
%(bb tex '(allpos allpos1 tack))
\vbox{
\hbox{\hskip0\unit $/allpos\// /v\// ← /allpos1\//[/v\//, 1]$}
\medskip

\hbox{\hskip0\unit $/allpos1\//[/v\//, /n\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v\// \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v\// \qthen  </n\//> \qcons 
 /allpos1\//[\qd /v\//, /add1\// /n\//]$}
\hbox{\hskip4\unit $    \qelse  </n\//> \qcons  [/tack\//[/n\//, /allpos\// 
\qa /v\//] * /allpos1\//[\qd /v\//, /add1\// /n\//]]$}
\medskip

\hbox{\hskip0\unit $/tack\//[/n\//, /w\//] ← \qif  \qn /w\// \qthen  \qNIL 
 \qelse  [/n\// \qcons  \qa /w\//] \qcons  /tack\//[/n\//, \qd /w\//]$}
}
$$

Now we modify to /allpos/ and /allpos1/ to carry around the parameter /u/ 
and rule out those positions that don't agree.  In particular
we only add $<n>$ to the list if $/agrees/[/u/,/v\//]$ is satisfied, and in
this case we don't look for agreement in \qa/v/ as the top level
match makes this impossible (recall our lists are finite tree-like structures).
So we arrive at the following:
$$
\label{fcnallsubsub}
%(bb tex '(allsubsub allsubsub1))
\vbox{
\hbox{\hskip0\unit $/allsubsub\//[/u\//, /v\//] ← /allsubsub1\//[/u\//, 
/v\//, 1]$}
\medskip

\hbox{\hskip0\unit $/allsubsub1\//[/u\//, /v\//, /n\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v\// \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /agrees\//[/u\//, /v\//] \qthen  </n\//> 
\qcons  /allsubsub1\//[/u\//, \qd /v\//, /add1\// /n\//]$}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v\// \qthen  /allsubsub1\//[/u\//, 
\qd /v\//, /add1\// /n\//]$}
\hbox{\hskip4\unit $    \qelse  /tack\//[/n\//, /allsubsub\//[/u\//, \qa 
/v\//]] * /allsubsub1\//[/u\//, \qd /v\//, /add1\// /n\//]$}
}
$$

An alternate solution for the /allpos/ and the /allsubsub/ problems
is to pass along a complete representation of the current position.  
When we pass it in the \qd /v/ direction we need to add 1 to the
last element and when we pass it in the \qa/v/ direction we need to
add a 1 to the end of the list.  Since all of the action is at the
end of the list it is easier to pass along the reverse of the position
list and re-reverse it when returning the position as an answer.  
Thus we get the following definitions 
$$
\label{fcnallpos1}\label{fcnallsubsub1}
%(bb tex '(allpos% allpos1% allsubsub% allsubsub1%))
% Don't forget to remove the % signs from the following defs
\vbox{
\hbox{\hskip0\unit $/allpos/ /v/ ← /allpos1/[/v/, |(1)|]$}
\medskip
\hbox{\hskip0\unit $/allpos1/[/v/, /p\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v/ \qthen  $}
\hbox{\hskip8\unit $        /reverse/ /p/ \qcons  /allpos1/[\qd /v/, /add1/ 
\qa /p/ \qcons  \qd /p\//]$}
\hbox{\hskip4\unit $    \qelse  /reverse/ /p/$}
\hbox{\hskip10\unit $          \qcons  [/allpos1/[\qa /v/, 1 \qcons  /p\//]$}
\hbox{\hskip13\unit $             * /allpos1/[\qd /v/, /add1/ \qa /p/ 
\qcons  \qd /p\//]]$}
\medskip
\hbox{\hskip0\unit $/allsubsub/[/u/, /v\//] ← /allsubsub1/[/u/, /v/, |(1)|]$}
\medskip
\hbox{\hskip0\unit $/allsubsub1/[/u/, /v/, /p\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /agrees/[/u/, /v\//] \qthen  $}
\hbox{\hskip8\unit $        /reverse/ /p/ \qcons  /allsubsub1/[/u/, \qd 
/v/, /add1/ \qa /p/ \qcons  \qd /p\//]$}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v/ \qthen  /allsubsub1/[/u/, 
\qd /v/, /add1/ \qa /p/ \qcons  \qd /p\//]$}
\hbox{\hskip4\unit $    \qelse  /allsubsub1/[/u/, \qa /v/, 1 \qcons  /p\//]$}
\hbox{\hskip10\unit $          * /allsubsub1/[/u/, \qd /v/, /add1/ \qa 
/p/ \qcons  \qd /p\//]$}
}
$$

Notice that in the first solution, the construction of the position representation
was taken care of somewhat automatically by the recursive structure of the program,
while in the second case we had to worry about the details of constructing
the position representations.

In both cases the computation works by passing information both down and across
the list structure and getting results back.  What is passed on and the 
interpretation of the result returned depends on the direction. 
In this example there is no exchange of information between the subcomputations.
In a more complicted situation this might also be necessary.

\section{Lots of LISP functions to program.}
\label{writinex}


	The following are descriptions of functions on lists and S-expressions.
You should write LISP programs to compute these functions.  A description
of the form  ``$/foo/[/x\//]$ is true if and only if $\ldots$ ''
means your program should
return \qT\ in the case that $/foo/[/x\//]$ is true and \qNIL\ otherwise.
Write your solutions out in external form, if you like, then
convert them to internal form and try them out in whatever LISP system
you have access to.   You should convince yourself by some informal
process of reasoning that your solutions are indeed correct.  You
will be asked to prove various facts about your programs after you
have studied Chapter (SECTION PROVIN).  This should encourage you to
write clean, understandable programs and document them carefully
so you will remember why you thought they were correct to begin with
and what tricks you may have employed.


	The problems are classified according to the intended interpretation
of the lists or S-expressions.  The classes include lists, S-expressions,
arithmetic expressions, polynomials, (finite) sets, permutations, trees, and graphs.
Each group begins with some simple problems (with one line solutions)
to get you going.  For the more complicated functions, you will find
that defining auxiliary functions is useful.  Towards the end the programs
may require a fair amount of thinking to get things organized correctly,
but none of the problems require really lengthy programs.
Pay attention to getting the trivial cases (e. g. when some of the arguments
are \qNIL\ or atomic or otherwise to be considered basic) correct.  It is 
in general important to understand the trivial cases in the computation
of a function.

	The observant reader will no doubt notice that some of these
functions are defined in later chapters.  Thus you will have some
cases where you can compare your solution to those given.   (Pointers
to these definitions can be found in the function index.)
%Restore some TeX definitions, remove these when Latex is flushed.
\def\centerline#1{\begin{center}#1\end{center}}
\def\item{\par\hang\textindent}
\def\itemitem{\par\indent \hangindent2\parindent \textindent}
%  end of definitions to be removed
\medskip
\newcount\excount\excount=0
\def\startex{\medskip\advance\excount by 1\item{\the\excount.}}
\centerline{\bf Lists}
\startex $/samelength/[/u/,/v\//]$ tests whether the lists /u and /v have the same 
length.
$$samelength[|(A B C), (D E F)|] = \qT$$
$$samelength[|(A B C), (A C)|] = \qNIL$$
    Do not use any operations or tests on numbers to write your program.


\startex $/prup/[/u/,/v\//]$ 
is the list formed by pairing the corresponding elements
of the lists /u/ and /v/.  Thus

$$/prup/[|(X Y Z)|, |(1 A (FOO BAR))|] 
= |((X . 1) (Y . A) (Z FOO BAR))|.$$

\iffalse
\startex $/assoc-inverse/[/x/,/a\//]$ is a list of expressions associated with /x/ in 
the list of pairs (association-list) /a/.  Thus 
$$/assoc-inverse/[|(OR A B)|,|((P AND A C) (Q OR A B) (R IMPLIES C B) (S OR A B))|]
= |(Q S)|$$
$$/assoc-inverse/[|1|,|((X . 2) (Y . 0))|] = \qNIL\  .$$
\fi

\startex $/istail/[/u/,/v\//]$ is true if and only if the list /u/ is a tail of /v/.  
That is
when /cdr\//ing through /v/ you will eventually get to /u/.  

\startex $/commontail/[/u/,/v\//]$ is the longest common sublist of
/u/ and /v/ ending with the ends of the lists.  Thus

$$/commontail/[|(A B C D E)|,|(A C D E)|] = |(C D E)|.$$

\startex $/upto/[/u/,/v\//]$ 
when /u/ is a tail of /v/, is the list of elements of /v/ 
up to the point where /u/ begins.  Thus

$$/upto/[|(C D E)|,|(A B C D E)|] = |(A B)|.$$

\iffalse
\startex $/nth/[/u/,/n\//]$ is the /n\//th element of the list /u/.  

\startex $/nthpos/[/u/,/n\//]$ is the sublist of /u/ beginning with the /n\//th element.

\startex $/least/[/u\//]$ is the least integer in the list /u/ of integers.
\fi

\startex $/mapapp/[/f/,/u\//]$ appends together the lists obtained by applying /f/ 
to successive
elements of /u/.  

\startex $/mapchoose/[/p/,/u\//]$ forms a list of those elements of /u/ satisfying /p/.  

\startex $/partition/[/u/,/n\//]$ is the list of partitions of the list /u/ into
/n/ sublists /u1/ $\ldots$ /un/ such that $/u1/*[/u2/*\ldots*/un\//]=/u/$.  
If /n/ is greater than the length of /u/ then your program should return
an error message of some kind.
Thus 
$$/partition/[|(A B C)|,2]=|((A) (B C))((A B) (C)))|$$
   Write a program /testpart/ to test the result returned by /partition/.  
For each partition, /testpart/ should append together the lists /ui/
and check that the result is /u/.  

\medskip
\centerline{\bf S-expressions}

\startex $/mirror/[/x\//]$ returns the mirror image of an S-expression /x/.  
Thus 
$$/mirror/[|((A.B).(C.D))|]=|((D.C).(B.A))|.$$

\startex $/occur/[/x/,/y\//]$ is true if and only if the atom /x/ occurs in the S-expression 
/y/.  For example

$$/occur/[|B|, |((A.B).C)|] = \qT.$$

\startex $/multiplicity/[/x/,/y\//]$ is the number of times the atom /x/ occurs in 
the S-expression /y/.  

\iffalse
\startex $/set-of-atoms/[/x\//]$ is a list without duplications of the atoms occurring in 
the S-expression /x/. 

\startex $/bag-of-atoms/[/x\//]$ is a list of all atoms that occur in the
S-expression /x/ paired with their multiplicities.
\fi
\item{}
        A path in an S-expression /x/ is a list of |A|'s and |D|'s such that you can
apply a succession of \qa's or \qd's to /x/ (according to whether the next list
element is |A| or |D|)  without trying to apply \qa\ or \qd\ to an atom.  We say
that the resulting subexpression is at the end of the path or that the path leads
to that subexpression.  Thus 
|(A D)| is a path in |((X . (Y . Z)) . F)|  but |(D A)| is not.
Also |(Y . Z)| is at the end of the path |(A D)| in |((X . (Y . Z)) . F)|.

\startex $/ispath/[/p/,/x\//]$ is true if and only if /p/ is a path in /x/.  

\startex $/depth/[/x\//]$ is the length of the longest path leading to an atom in the 
S-expression /x/.  
$$/depth/[|(((A . B) . C) . D|] = 3.$$

        We say that an S-expression is balanced if it is an atom or if
$/depth/[\qa\ /x\//]$ and $/depth/[\qd\ /x\//]$ differ by at most 1
and \qa\ /x/ and \qd\ /x/ are both balanced.  

\startex $/balanced/[/x\//]$ is true if and only if the S-expression /x/ is balanced.

\startex $/balance/[/x\//]$ is balanced and has the same fringe as /x/.

\startex $/get/[/y/,/p\//]$ is the subexpression at the end of the path /p/ in the
S-expression /y/.  Thus
$$/get/[|(A ((B) C) (B))|,|(D A A)|] = |(B)|.$$

\startex $/point/[/x/,/y\//]$ is the path in the S-expression /y/
leading to the left-most 
occurrence of the S-expression /x/ in the S-expression /y/. Thus
$$/point/[|(B)|,|(A ((B) C) (B))|] = |(D A A)|.$$

\startex $/allpoint/[/x/,/y\//]$ is a list of all paths /p/
such that $/get/[/y/,/p\//]=/x/$.  Thus
$$/allpoint/[|(B)|,|(A ((B) C) (B))|] = |((D A A) (D D A))|.$$

\startex $/commons/[/x\//]$ is a list of the subexpressions of the S-expression
/x/ that occur more than once in /x/, each followed by a list of the points 
(paths leading to the points) where it occurs. 

\iffalse
\startex Let /a/ be an association list pairing variables (atoms satisfying /isvar/)
their associated values (arbitrary S-expressions).  $/sublis/[/x/,/a\//] $
replaces every occurrence of a variable in the S-expressions /x/ with
its associated value in /a/.  This is done by ``simultaneous'' rather that
``sequential'' substitution so that if the value associated with a variable
happens to have a variable in it, that occurrence of the variable will 
remain in the result.

\startex Let /p/ be an S-expression with certain of the atoms
occurring /p/ regarded as variables, e.g. those atoms satisfying /isvar/
as in the previous problem.  For any S-expression /x/, if
there are substitutions for the variables in /p/  that
make /p/ and /x/ the same expression, then $/match/[/x/,/p\//]$ is a list of pairs
such that
$$/sublis/[/p/,/match/[/x/,/p\//] = /x/$$

    Otherwise, $/match/[/x/,/p\//] = |NO|$.  For example,
$$/match/[|(PLUS(TIMES X Y) Z)|,|(PLUS \&X \&Y)|] = |((\&X TIMES X Y) (\&Y . Z))|$$
where only the atoms |\&X| and |\&Y| are regarded as variables.
\fi
\medskip
\centerline{\bf Symbolic arithmetic and algebra}

\startex Let a polynomial in /x/ be represented by a list of its coefficients
in order of ascending powers of /x/.  Thus $x↑3+x+5$ is represented
by |(5 1 0 1)|.  
	\itemitem{\the\excount.1.} $/sum/[/u/,/v\//]$  is the sum
	\itemitem{\the\excount.2.} $/prod/[/u/,/v\//]$ is the product 
	\itemitem{\the\excount.3.} $/quot/[/u/,/v\//]$ is the quotient 
	\itemitem{\the\excount.4.} $/rem/[/u/,/v\//]$ is the remainder 
\indent
of the polynomials /u/ and /v/ in the same notation.


\startex  Consider arithmetic expressions as represented in this chapter.
Namely an expression is 
\ialign{\hbox to 32pt{\hfil #}\quad&#\hfil\cr
(i)&a number (satisfies /numberp/), \cr
(i)&a variable (not a number and satisfies \qat),\cr
(iii)&a sum :$(|PLUS|\qcons<\hbox{\rm list of expressions}>)$, or\cr
(iv)&a product :$(|TIMES|\qcons<\hbox{\rm list of expressions}>$.\cr
}
    (For simplicity, assume the sum and product lists always have at least 
2 elements.)
\item{}
	The function /sop/ converts such expressions into sum of products
form, eg. the resulting expression is either a monomial 
or a sum of monomial terms which has the form 
$(|PLUS|\qcons<\hbox{list of monomials}>)$.
A monomial is either a number, a variable, or a product of the 
form $(|TIMES|\qcons<\hbox{list of numbers or variables}>)$.

	Try your simplifier on expressions returned by /diff/.
\medskip
\centerline{\bf Sets}

\startex Lists can be thought of as representing finite sets using the
the program $/member/[/x/,/u\//]$ defined earlier, to compute the membership
relation.   Write programs to compute the functions
union, $u\cup v$, intersection, $u\cap v$, and the set difference, $u-v$,
for lists /u/ and /v/ viewed as representing sets.  For example:
$$|(A B C) ∪ (B C D) = (A B C D)|,$$
$$|(A B C) ∩ (B C D) = (B C)|,    $$
and
$$|(A B C) - (B C D) = (A)|.      $$
\item{}
[Remark: 
There are a couple of possible conventions for representing finite sets as lists.  
One is to require S-expressions representing elements of a set to occur in the 
representing list exactly once.   The other is to allow multiple occurrences
of an S-expression representing an element of the set.  You should decide
which convention you wish to adopt, and make sure your programs are consistent
with that convention]

\startex Suppose /x/ takes numbers as values and /u/ takes as
values lists of numbers in ascending order, e.g. |(2 4 7)|.  Write a
function $/insert/[/x/, /u\//]$ whose value is obtained from that of /u/ by
putting /x/ in /u/ in its proper place.   Thus
$$insert[3, |(2 4)|] = |(2 3 4)|$$, 
and 
$$insert[3, |(2 3)|] = |(2 3 3)|.$$

\startex Write functions giving the union, intersection, and set
difference of ordered lists; the result is wanted as an ordered list.
\item{}
	Note that computing these functions of unordered lists takes
a number of comparisons proportional to the square of the number of
elements of a typical list, while for ordered lists, the number of
comparisons is proportional to the number of elements.

\startex Using /insert/, write a function /sort\// that transforms an
unordered list into an ordered list.

\startex Write a function /goodsort\// that sorts a list using a
number of comparisons proportional to $n\log n$, where /n/ is the
length of the list to be sorted.

\medskip
\centerline{\bf Permutations}

\startex $/rcycle/[/u\//]$ is obtained from the list /u/ by moving the
last element to the first position.  Thus
$$/rcycle/[|(A B C D)|] = |(D A B C)|.$$

\startex $/lcycle/[/u\//]$  is obtained from the list /u/ by moving the
first element to the last position.  Thus
$$/lcycle/[|(A B C D)|] = |(B C D A)|.$$ 

\item{}
        We can think of a permutation on /n/ objects as a function which maps
a list |(l1 l2 ... lN)| of /n/ distinct elements 
to a list containing the same elements in  a
different order.  Thus  |(3 4 1 2)| is a permutation of |(1 2 3 4)| and
|(FOO BAR BAZ)| is a permutation of |(BAR BAZ FOO)|.
The permutation itself can be represented as a list in several ways.
We describe two possible representations of a permutation /pi\//.
\item{}
	|REP1:| /pi\// is represented as a list of numbers |(j1 j2 ... jN)| 
which is itself a permutation of the list |(1 2 ... N)| and the result of 
applying such a permutation to a list /u/ of length /n/ is the list $u'$
where the $k$th element of $u'$ is the $jk$th element of /u/.  
Thus the permutation |(2 3 4 1)| applied to the list |(A B C D)|
is the list |(B C D A)|.  |(1 2 3 4)| is the identity permutation.
\item{}
	|REP2:| /pi\// is represented as a list of disjoint cycles, 
where a cycle is a a list of length at most /n/ of numbers between 1 and /n/ 
(with no two elements the same).  The permutation represented by such a
list of cycles is the permutation that results from applying each of the cycles.
(The order of application doesn't matter since the cycles are disjoint.)
The result of applying a cycle |(j1 j2 ... jk)| 
to a list /u/ of length /n/ is the list $u'$ where the element in position
/jm/ in $u'$ is the element in position $/jm/-1$  in /u/ for $1≤m≤k$
(taking /j0/ to be /jk/).  Elements in positions not mentioned 
in the cycle are unchanged.
Thus the cycle  |(1 4 2)| applied to |(A B C D)| gives |(B D C A)|.
The empty list of cycles is the identity permutation in this representation.

\startex $/isperm1/[/pi\//,/n\//]$ ($/isperm2/[/pi\//,/n\//]$) is true just if the list /pi\// 
represents 
a permutation on /n/ objects according to |REP1| (|REP2|).

\startex $/sameperm2/[/pi1/,/pi2\//]$ is true if and only if /pi1/ and /pi2/
represent the same
permutation.  (Note that the representation by |REP2| is not unique
while in |REP1| it is.)

\startex $/rho12/[/pi\//]$ maps a list /pi\// representing a permutation according to
|REP1| to a list representing the same permutation according to |REP2|.
/rho21/[/u\//] is the inverse map.  

\startex $/compose1/[/pi1/,/pi2\//]$ represents the permutation that results if /pi2/
is applied followed by /pi1/, all represented according to |REP1|.
/compose2/[/u/,/v\//] does the same but using |REP2|.

\startex $/invert1/[/pi\//]$ ($/invert2/[/pi\//]$) is the inverse to the permutation /pi\//,
in |REP1| (|REP2|).  Thus $/compose1/[/invert1/[/pi\//],/pi\//]$ is the identity
permutation.
\item{}
        Note that one way to solve the above problems would be to write the
programs for one representation and use the transformations /rho12/ and /rho21/
to obtain those for the other representation.  However part of the
purpose of the exercise is to see how the different representations behave and
this solution would defeat that purpose.
\medskip
\centerline{\bf Trees}
\item{}
	 Consider a tree structure represented as a list in the following
way.  A leaf is any list of the form |(LEAF e)| where |e| is any
S-expression.  A tree is either a leaf, or a list of trees.

\startex  /leaves/[/t\//] is a list of all the leaves in the tree /t/, in the same
order as they appear in  the tree.  (Compare to /fringe/ for S-expressions.)

\startex  Let /leafval/ be an evaluation function on leaves.  (Assume /leafval/
returns integers.)
/bestleaf/[/t\//] is a leaf of /t/ having a maximal value according /leafval/.
That is no other leaf of /t/ has a better value.

\startex $/bestleaf1/[/t\//]$ is a leaf of /t/ of maximal value and among those of
the same value, /bestleaf1/[/t\//] has least depth (is closest to the root).
\medskip
\centerline{\bf Graphs}
\item{}
	Let /g/ be a directed graph represented as a list of lists as described
earlier in this chapter.

\startex $/isnext/[/u/,/v/,/g\//]$ is true if and only if /g/
contains an edge from /u/ to /v/.  

\startex $/successors/[/u/,/g\//]$ is the list of vertices, /v/, in /g/
such that $/isnext/[/u/,/v/,/g\//]$.

\startex $/predecessors/[/u/,/g\//]$ is the list of vertices /v/, in /g/
such that $/isnext/[/v/,/u/,/g\//]$.

\startex $/undir/[/g\//]$ is true if and only if /g/
is undirected.  That is, if for every
edge from /u/ to /v/ in /g/ there is also and edge from /v/ to /u/.  

\startex $/mkundir/[/g\//]$ is the graph /g1/
with the same vertices as /g/, and  such that
there is an edge from /u/ to /v/ in /g1/ if and only if /g/ has either an edge from
/v/ to /u/ or and edge from /u/ to /v/.  

\startex  If /g/ is undirected then
$/delete-vertex/[/v/,/g\//]$  returns a graph /g1/ with vertices those of
/g/ omitting /v/, and edges the same as /g/ omitting those connecting /v/ to 
another vertex. 

\startex If /g/ is undirected then
$/complement/[/g\//]$  returns a graph /g1/ with vertices the same as /g/, but
vertices /v/ and /w/ are joined by an edge in /g1/ if and only if they are not
joined by an edge in /g/.

\startex For any graph /g/, $/reachable/[/u/,/v/,/g\//]$ 
is true if and only if there is a
sequence of vertices /u1/, /u2/,$\ldots$,/un/ in /g/ with /u/ = /u1/, 
/v/ = /un/ and
$/isnext/[/ui/,$/ui/+1$,/g\//]$ for $1≤i≤n-1$.  

\startex For any graph /g/,
$/conn/[/g\//]$ 
is true if and only if the directed graph /g/ is connected in the sense
that every vertex is reachable from every other vertex.  
\item{}
NB:  Graphs in general have cycles, so when you are recurring through a graph
you need to keep track of where you have been in order to avoid a forever
looping program.